class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        n = len(candidates)
        ans = []
        path = []
        # [1, 1, 2, 5, 6, 7, 10]
        def dfs(i, goal):
            # 所选元素之和恰好等于 target
            if goal == 0:
                ans.append(path.copy())
                return
            # 没有可以选的数字
            if i == n:
                return
            # 所选元素之和无法恰好等于 target
            x = candidates[i]
            if goal < x:
                return

            # 选
            path.append(x)
            dfs(i + 1, goal - x)
            path.pop()

            # 不选
            i += 1
            while i < n and candidates[i] == x:
                i += 1
            dfs(i, goal)
        
        dfs(0, target)
        return ans